package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/16/20 2:27 PM
 */
public class Mirrors_01 {

    private interface CallBack<T>{

        public void callBack(T t);
    }

    public static void inorderTraversal(TreeNode root) {


        if (root == null) {

            return;
        }

        TreeNode node = root;
        TreeNode preNode = null;
        while (node != null) {


            if (node.left != null) {

                preNode = node.left;

                while (preNode.right != null && preNode.left != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    /**
                     * 第一次到达preNode的节点
                     */
                    preNode.right = node;
                    node = node.left;
                }else {

                    /**
                     * 第二次到达preNode节点
                     */
                    preNode.right = null;
                    System.out.println(node.val);
                    node = node.right;
                }


            }else {

                System.out.println(node.val);
                /**
                 * 这里的node.right 一定有值，除了最后一个，即退出循环
                 *
                 */
                node = node.right;
            }

        }

    }

    public static void postOrderTraversal(TreeNode root) {


        if (root == null) {

            return;
        }

        TreeNode dump = new TreeNode(0);

        dump.left = root;

        TreeNode node = dump,preNode = null;

        while (node != null) {

            if (node.left != null) {

                // 说明有左子树
                preNode = node.left;

                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    // 第一次到这里,设置node的前序节点
                    preNode.right = node;
                    node = node.left;
                }else {

                    // 逆序遍历 从 node.left 到 preNode
                    if (node.left != preNode) {
                        printTreeNode(node.left, preNode, new CallBack<TreeNode>() {
                            @Override
                            public void callBack(TreeNode node) {

                                System.out.println(node.val);
                            }
                        });

                    }else {
                        System.out.println(preNode.val);
                    }

                    // 第二次到这里，说明node的左边遍历完成，遍历右边
                    preNode.right = null;
                    node = node.right;
                }
            }else {

                // 没有左子树，转到右边
                node = node.right;
            }
        }
    }

    private static void printTreeNode(TreeNode from,TreeNode to,CallBack<TreeNode> callBack) {


        reversal(from,to);

        TreeNode node = to;

        while (true) {

            callBack.callBack(node);

            if (node == from) {

                break;
            }
            node = node.right;
        }

        reversal(to,from);
    }

    private static void reversal(TreeNode from,TreeNode to) {

        TreeNode node = from;

        while (node != to) {

            TreeNode nodeRight = node.right;
            nodeRight.right = node;
            node = nodeRight;
        }

    }
}
